package com.leetcode.algs4.string;

/**
 * @author Dennis Li
 * @date 2020/7/8 21:20
 */
public class MSD {
    private static final int R = 256;
    private static final int M = 15;// 小数组切换的阈值
    private static String[] aux;

    private static int charAt(String s, int d) {
        return d < s.length() ? s.charAt(d) : -1;
    }

    public static void sort(String[] a) {
        int N = a.length;
        aux = new String[N];
        sort(a, 0, N - 1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d) {
        // 以第d个字符为键将a[lo]至a[hi]排序
        if (hi <= lo + M) return;

        int[] count = new int[R + 2];
        for (int i = lo; i < hi; i++) {
            count[charAt(a[i], d) + 2]++;
        }
        for (int r = 0; r < R + 1; r++) {
            count[r + 1] = count[r];
        }
        for (int i = lo; i <= hi; i++) {
            // 数据重写
            a[i] = aux[i - lo];
        }
        // 递归的以每个字符为键进行排序
        for (int r = 0; r < R; r++) {
            // 依次后移一位再进行排序
            sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
        }
    }

}
